
//15.三数之和
class Solution {
public:

    vector<vector<int>> threeSum(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());  //进行排序
        vector<vector<int>> ret;
        if(nums[0]>0||nums[n-1]<0) return ret;  //当最大值<0以及最小值>0不可能存在满足的数组
        for(int i=0;i<n-2;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;    //当前数与上一个就不需要对当前数进行处理，
                                                    //否则三元组会重复
            if(nums[i]+nums[i+1]+nums[i+2]>0) break;   //当最小的三个数之和>0没有三元组了
            if(nums[i]+nums[n-1]+nums[n-2]<0) continue;   //当最小的数与最大的两个数相加<0，当前的i与任何数都不能进行匹配
        
            int left=i+1,right=n-1;   //进行两数之和
            while(left<right)
            {
                if(nums[left]+nums[right]+nums[i]>0) right--;       
                else if(nums[left]+nums[right]+nums[i]<0) left++;
                else 
                {
                    ret.push_back({nums[left],nums[right],nums[i]});
                    left++;
                    while(left<right&&nums[left]==nums[left-1]) left++;  //跳过重复的数据
                    right--;
                    while(left<right&&nums[right]==nums[right+1]) right--;  
                }
            }
        }
        return ret;
    }
};